package leetcode.leetcode_hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * @ClassName T0279
 * @Description 完全平方数
 * @Author Fanxc
 * @DATE 2021/6/21 21:46
 * @Version 1.0
 */
public class T0279 {
    //动态规划
    class Solution1 {
        public int numSquares(int n) {
            int ssize=(int)Math.sqrt(n)+1;
            int[] snums=new int[ssize];
            //snums存着每个数的平方数值
            for(int i=1;i<ssize;i++){
                snums[i]=i*i;
            }
            int[] dp=new int[n+1];
            //初始化dp数组每个值为极大值
            Arrays.fill(dp, Integer.MAX_VALUE);
            //n=0时，结果是0个平方数
            dp[0]=0;
            //1..n，逐个计算dp[i]
            for(int i=1;i<=n;i++){
                for(int j=1;j<ssize;j++){
                    if(snums[j]>i){
                        break;
                    }
                    dp[i]=Math.min(dp[i],dp[i-snums[j]]+1);
                }
            }
            return dp[n];
        }
    }
    //贪心枚举
    class Solution2 {
        //创建存储平方数的数组
        HashSet<Integer> set;

        public int numSquares(int n) {
            set=new HashSet<>();
            //平方数数组 初始化赋值
            int ssize=(int)Math.sqrt(n)+1;
            for(int i=1;i<=ssize;i++){
                set.add(i*i);
            }

            int count=1;
            for(count=1;count<=n;count++){
                //n能被拆分成count个平方数
                if(is_divided_by(n, count)){
                    return count;
                }
            }

            return count;
        }

        //返回值为boolean的判断n的完全平方数count
        boolean is_divided_by(int n,int count){
            //递归终止条件
            if(count==1){
                return set.contains(n);
            }

            for(Integer s:set){
                //
                if(is_divided_by(n-s,count-1)){
                    return true;
                }
            }
            return false;
        }
    }
    //贪心+BFS
    class Solution3 {
        public int numSquares(int n) {
            //存储平方数
            //这次必须是有序的，所以用ArrayList数组，我本来用Set解答错误
            ArrayList<Integer> square_nums=new ArrayList<>();
            for(int i=1;i*i<=n;i++){
                square_nums.add(i*i);
            }
            //队列
            HashSet<Integer> queue=new HashSet<>();
            //初始化队列
            queue.add(n);
            //计数
            int value=0;

            while(queue.size()>0){
                value++;
                HashSet<Integer> next_queue=new HashSet<>();
                for(Integer a:queue){
                    for(Integer b:square_nums){
                        if(a<b){
                            break;
                        }
                        //队列中的数是平方数：已找到解，返回value
                        else if(a.equals(b)){
                            return value;
                        }
                        //队列中的数不是平方数：减去平方数，并加入下一轮队列
                        else{
                            next_queue.add(a-b);
                        }
                    }
                }
                //迭代队列
                queue=next_queue;
            }
            return value;
            //其实根本走不到这一步，循环里一定返回了，所以这里返回啥都行
        }
    }
}
